package com.gxc.array;

/**
 * 给定一个数组arr长度为N，你可以把任意长度大于0且小于N的前缀作为左部分，剩下的作为右部分。
 * 但是每种划分下都有左部分的最大值和右部分的最大值，
 * 请返回最大的，左部分最大值减去右部分最大值的绝对值。
 *
 * 解法：
 * 1.尝试以每个位置n作为数组arr的左部分最大值，剩余作为右部分,求剩余右部分的最大值，
 * 如果n不能作为左部分最大值的最大值，则也划入左部分，求剩余右部分的最大值
 * 可用预处理数组，准备两个数组，存放i位置作为左部分时，最大值，i位置作为右部分时，最大值
 * 时间复杂度是O(N)，额外空间复杂度也是O(N)
 */
public class MaxLeftRight {

    public static void main(String[] args) {

    }

    /**
     * 时间复杂度是O(N)，额外空间复杂度也是O(N)
     * 尝试以每个位置n作为数组arr的左部分最大值，剩余作为右部分,求剩余右部分的最大值，
     * 如果n不能作为左部分最大值的最大值，则也划入左部分，求剩余右部分的最大值
     * 可用预处理数组，准备两个数组，存放i位置作为左部分时，最大值，i位置作为右部分时，最大值
     * @param arr
     * @return
     */
    public static int leftMinusRight(int[] arr) {
        if (arr == null || arr.length==0) return 0;

        int length = arr.length;
        //i作为左部分的最大值
        int[] leftMax = new int[length];
        leftMax[0] = arr[0];
        for (int i = 1; i < length; i++) {
            leftMax[i] = arr[i]>leftMax[i-1]?arr[i]:leftMax[i-1];
        }
        //i作为右部分的最大值
        int[] rightMax = new int[length];
        rightMax[length-1] = arr[length-1];
        for (int i = length-2; i>=0; i--) {
            rightMax[i] = arr[i]>rightMax[i+1]?arr[i]:rightMax[i+1];
        }
        //i作为左部分分界线时，求最大值
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < length-1; i++) {
            max = Math.max(max, Math.abs(leftMax[i] - rightMax[i+1]));
        }
        return max;
    }

    /**
     * 时间复杂度是O(N)，额外空间复杂度是O(1)
     * 已知左右部分都必须有值，数组也必定存在一个最大值部分，所以就是找另一部分的最小值。最大值-最小值就是最大的值。
     * 当最大值在左部分时，求右部分的最小值，右部分的最小值肯定包含 n-1 位置的值，
     * 所以不管右部分怎么划分，n-1的值肯定是右部分最小值的下限，就变成  数组最大值  - （n-1）位置 的值
     * 当最大值在右部分时，求左部分的最小值，左部分的最小值肯定包含 0 位置的值，
     * 所以不管左部分怎么划分， 0的值肯定是左部分最小值的下限，就变成  数组最大值  - （0）位置 的值
     * 比较这两个值的大小即可
     * @param arr
     * @return
     */
    public static int leftMinusRight2(int[] arr) {
        if (arr == null || arr.length==0) return 0;

        //循环一遍查找最大值
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }

        return Math.max(Math.abs(max - arr[0]), Math.abs(max - arr[arr.length-1]));
    }

}
